package 典型.回溯法;

import java.util.ArrayList;
import java.util.List;

// 组合问题 C42
public class LC77 {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> combinations = new ArrayList<>();
        backtracking(n, 1, k, combinations, new ArrayList<Integer>());
        return combinations;
    }

    //n即取值范围为1-n
    //start表示可以从哪个数取值，只能取大于等于start
    //k表示还需要多少个数
    //combinations要返回的结果
    //combineList存放一种排列
    private void backtracking(int n, int start, int k, List<List<Integer>> combinations, List<Integer> combineList) {
        //k == 0，表示找到了已经找到k个数组成一种排列
        if (k == 0) {
            combinations.add(new ArrayList<>(combineList));
            return;
        }
        //i从start开始到n-k+1,这个地方n-k+1表示最多只能取到这个数值，如果这个位置取得值超过n-k+1，那么后面剩下的数不够k-1个，显然不能符合要求
        for (int i = start; i <= n - k + 1; ++i) {
            combineList.add(i);
            backtracking(n, i + 1, k - 1, combinations, combineList);
            combineList.remove(combineList.size() - 1);
        }
    }

    public static void main(String[] args) {
        LC77 lc77 = new LC77();
        System.out.println(lc77.combine(10, 3));
    }
}
